#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

ugly_list = [1]      # cache ugly number
ugly_nth = [[0,0,0]] # cache nth


class Solution:
    """
    @param n: An integer
    @return: the nth prime number as description.
    """

    # ugly_list = [1]      # cache


    def nthUglyNumber(self, n):
        # write your code here
        len_ugly = len(ugly_list)

        if len_ugly >= n:
            return ugly_list[n-1]

        cur_max_ugly = ugly_list[len_ugly-1]
        while len_ugly < n:
            cur_max_ugly = self.get_next(cur_max_ugly + 1)
            ugly_list.append(cur_max_ugly)
            len_ugly += 1

        return cur_max_ugly

    @staticmethod
    def get_next(base):
        while True:
            if Solution.is_ugly(base):
                return base
            else:
                base += 1

    @staticmethod
    def is_ugly(num):
        assert num >= 2
        # nlist = [25, 24, 9, 4, 2, 3, 5]
        nlist = [2, 3, 5]
        nth_ = [0, 0, 0]
        # while num % 2 == 0: num /= 2
        # while num % 3 == 0: num /= 3
        # while num % 5 == 0: num /= 5

        for n, divid in enumerate(nlist):
            while num % divid == 0:
                num /= divid
                nth_[n] += 1
        if num == 1:
            ugly_nth.append(nth_)
            return True
        return False

# def diff(l1, l2):
#     for

def main():
    from time import time
    from pprint import pprint

    print("start main")

    s = Solution()
    print(s.nthUglyNumber(6))
    print(s.nthUglyNumber(7))
    print(s.nthUglyNumber(8))
    print(s.nthUglyNumber(41))
    # print(ugly_list)

    # pprint(ugly_nth)

    # 打印差值
    print("=================== 次变化规律 =====================")
    print(' 变化         次       数')
    for n, value in enumerate(ugly_nth):
        if n != len(ugly_nth)-1:
            # print diff(ugly_nth[n+1], value
            print(list(map(lambda x,y : x-y, ugly_nth[n+1], value)), end='  ')
            print(ugly_nth[n+1], end='  ')
            print(ugly_list[n+1])

    # print(s.nthUglyNumber(11))

if __name__ == "__main__":
    main()
